//****************************************************************
//Autor:   Yimy Juarez 
//       Gustavo Castro
//       Ulil Coqti
//       Josue Barrientos
//    
//Seccion: 10
//Nombre del Archivo: Sorting.java
//Fecha de Modificacion:17/07/2012
//Descripcion:
//Modelado de clase encargada de ordenar objetos
//mediante la utilizaci�n de distintos algoritmos
//***************************************************************
/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package algoritmos;


/**
 *
 * @author Roberto
 *         Gustavo
 *         Ulil
 *         Josué
 */

public class Sorting {

   //-----------------------------------------------------------------
   //  Sorts the specified array of objects using the selection
   //  sort algorithm.
   //-----------------------------------------------------------------
    /**
     * Tomado de: http://www.algolist.net/Algorithms/Sorting/Bubble_sort
     * @param list the value of list
     */
    public static void swap(Comparable[] list,int i, int j)
    {
        Comparable temp;
        temp = list[i];
        list[i]=list[j];
        list[j]=temp;
        
    }
    /**
     *
     * @param list the value of list
     */
    public static void bubbleSort (Comparable[] list)
   {
      boolean swapped = true;
      int j = 0;
      Comparable tmp;
      while (swapped) {
            swapped = false;
            j++;
            for (int i = 0; i < list.length - j; i++) {                                       
                  if (list[i].compareTo(list[i + 1]) > 0) {                          
                        tmp = list[i];
                        list[i] = list[i + 1];
                        list[i + 1] = tmp;
                        swapped = true;
                  }
            }                
      }
        }

//-----------------------------------------------------------------
//  Sorts the specified array of objects using the insertion
//  sort algorithm.
//-----------------------------------------------------------------
 /**
  *
  * @param list the value of list
  */
 public static void insertionSort (Comparable[] list)
  {
      for (int index = 1; index < list.length; index++)
      {
         Comparable key = list[index];
         int position = index;

         //  Shift larger values to the right
         while (position > 0 && key.compareTo(list[position-1]) < 0)
         {
            list[position] = list[position-1];
            position--;
         }
            
         list[position] = key;
      }
   }

    
    /**
     *
     * @param numbers the value of numbers
     */
    public static void mergeSort (Comparable[] numbers)
   {
                
		int number = numbers.length;
		mergesort_(numbers, new Comparable[number],0, number - 1);
   }
 
    /**
     *
     * @param numbers the value of numbers
     * @param helper the value of helper
     * @param low the value of low
     * @param high the value of high
     */
    private static void mergesort_(Comparable[] numbers, Comparable[] helper, int low, int high) {
		// Check if low is smaller then high, if not then the array is sorted
		if (low < high) {
			// Get the index of the element which is in the middle
			int middle = (low + high) / 2;
			// Sort the left side of the array
			mergesort_(numbers, helper,low, middle);
			// Sort the right side of the array
			mergesort_(numbers, helper,middle + 1, high);
			// Combine them both
			merge(numbers, helper,low, middle, high);
		}
	}
    /**
     *
     * @param numbers the value of numbers
     * @param helper the value of helper
     * @param low the value of low
     * @param middle the value of middle
     * @param high the value of high
     */
    private static void merge(Comparable[] numbers, Comparable[] helper, int low, int middle, int high) {

		// Copy both parts into the helper array
		for (int i = low; i <= high; i++) {
			helper[i] = numbers[i];
		}

		int i = low;
		int j = middle + 1;
		int k = low;
		// Copy the smallest values from either the left or the right side back
		// to the original array
		while (i <= middle && j <= high) {
			if (helper[i].compareTo(helper[j])<= 0) {
				numbers[k] = helper[i];
				i++;
			} else {
				numbers[k] = helper[j];
				j++;
			}
			k++;
		}
		// Copy the rest of the left side of the array into the target array
		while (i <= middle) {
			numbers[k] = helper[i];
			k++;
			i++;
		}

	}
   
   
    /**
     *
     * @param list the value of list
     */
    private static int partition(Comparable[] list, int left, int right)
    {
    int i;
    int pivote;
    Comparable temp, valor_pivote;
 
    pivote = left;
    valor_pivote = list[pivote];
    for (i=left+1; i<=right; i++){
        if (valor_pivote.compareTo(list[i])>0){
                 pivote++;    
                temp=list[i];
                list[i]=list[pivote];
                list[pivote]=temp;
 
        }
    }
    temp=list[left];
    list[left]=list[pivote];
    list[pivote]=temp;
    return pivote;   
            
    }
    /**
     *
     * @param list the value of list
     * @param left the value of left
     * @param right the value of right
     */
    private static void quickSortRecursive(Comparable[] list, int left, int right)
    {
        int pivot;
        if(right>left)
        {
        pivot = partition(list,left,right);
        quickSortRecursive(list,left,pivot-1);
        quickSortRecursive(list,pivot+1,right);
        }
        
    }
    /**
     *
     * @param list the value of list
     */
    public static void quickSort (Comparable[] list)
    {
        quickSortRecursive(list,0,list.length-1);
    }

    
    

}

